package com.algorithm.kruskal;

import java.util.Arrays;

/**
 * @author xxy
 * @create 2021 3 26 16:21
 */
public class Kruskal {
    private int edgeNum;//边的个数
    private char[] vertexs;//顶点数组
    private int[][] matrix;//邻接矩阵
    private static final int INF=Integer.MAX_VALUE;
    public Kruskal(int[][] matrix,char[] vertexs){
        this.vertexs=vertexs;
        this.matrix=matrix;
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if(matrix[i][j]!=INF){
                    edgeNum++;
                }
            }
        }
    }

    //得到边的集合
    private EData[] getEdges(){
        int index=0;
        EData[] edges=new EData[edgeNum];
        for(int i=0;i<vertexs.length;i++){
            for (int j = i + 1; j < vertexs.length; j++) {
                if(matrix[i][j]!=INF){
                    edges[index++]=new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    //对边进行排序
    private void sortEdges(EData[] edges) {
        for(int i=0;i<vertexs.length-1;i++){
            for(int j=0;j<vertexs.length-1-i;j++){
                if(edges[j].weigh>edges[j+1].weigh){
                    EData temp=edges[j];
                    edges[j]=edges[j+1];
                    edges[j+1]=temp;
                }
            }
        }
    }
    //返回字符的位置
    private int getPosition(char ch){
        for (int i=0;i<vertexs.length;i++){
            if(vertexs[i]==ch){
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取下标为i的顶点的终点（），用于后面判断两个顶点的最大顶点是否相同
     * @param ends：数组就是记录了各个顶点对应的终点是哪个，ends数组是动态的变化
     * @param i 表示传入的顶点所以对应的下标
     * @return返回所对应的终点的下标
     */
    private int getEnd(int[] ends, int i) {
        while (ends[i]!=0){
            i=ends[i];
        }
        return i;
    }
    public void kruskal(){
        int index=0;//表示最后结果数组的索引
        int[] ends=new int[edgeNum];
        EData[] rets=new EData[edgeNum];
        EData[] edges=getEdges();
        Arrays.sort(edges,((o1, o2) -> o1.weigh-o2.weigh));
        //遍历edges数组
        for(int i=0;i<edgeNum;i++){
            int p1=getPosition(edges[i].start);
            int p2=getPosition(edges[i].end);
            //获取终点
            int m=getEnd(ends,p1);
            int n=getEnd(ends,p2);
            if(m!=n){
                ends[m]=n;//设置m在已有最小生成树中的终点
                rets[index++]=edges[i];
            }
        }
        System.out.println("结果为："+Arrays.toString(rets));
    }

    public static void main(String[] args) {
        char[] vertexs={'A','B','C','D','E','F','G'};
        int[][] matrix={
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        Kruskal kruskal = new Kruskal(matrix, vertexs);
        //没有排序
        System.out.println(Arrays.toString(kruskal.getEdges()));
        //排序
       EData[] edges=kruskal.getEdges();
       Arrays.sort(edges,(o1,o2)->{return o1.weigh-o2.weigh;});
       //kruskal.sortEdges(edges);
        //System.out.println("排序后"+Arrays.toString(edges));
        kruskal.kruskal();

    }

}
//边
class EData{
    char start;
    char end;
    int weigh;
    public EData(char start, char end, int weigh) {
        this.start = start;
        this.end = end;
        this.weigh = weigh;
    }
    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weigh=" + weigh +
                '}';
    }
}
